package stack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Stack;

public class InfixToSuffix {
    ToSuffixUtil util=  new ToSuffixUtil();
    @Test
    public void test(){
          //表达式需要用" "(空格)隔开,方便后续处理
        String infixExpression="1 + ( ( 2 + 3 ) * 4 ) - 5";
        //逆序将栈中结果拿出,便是后缀表达式
        Stack<String> suffixExpression = toSuffix(infixExpression);
        ArrayList<String> list = new ArrayList<>();
        while(!suffixExpression.empty()){
            list.add(suffixExpression.pop());
        }
        //逆序遍历list得到,后缀表达式
        for (int i=list.size()-1;i>=0;i--){
            System.out.print(list.get(i)+" ");
        }

    }
    public Stack<String> toSuffix(String infixExpression){
        Stack<String> transitStack = new Stack<>();//中转储蓄栈
        Stack<String> numStack = new Stack<>();//数字暂存站

        //先讲中缀表达式切割分装到数组中,方便后续调用
        String[] expressions = util.expressionArray(infixExpression);
        for (int index=0;index<expressions.length;){
            //首先鉴别以下当前字符的类别
            String expression=expressions[index];
             int currentElementStyle=util.styleOf(expression);
               if (currentElementStyle!=0){
                   //当前字符不是数子
                   switch (currentElementStyle){
                       case 1://加减
                           if (numStack.empty()){
                               //栈空
                               numStack.push(expression);
                               index++;
                           }else{
                               //栈非空,比较当前元素与栈顶元素的优先级
                               int topElementPriority =util.styleOf(numStack.peek());
                               if (topElementPriority==4){
                                   //左括号
                                   numStack.push(expression);
                                   index++;
                               }else if (topElementPriority>1){
                                   //栈顶运算符优先级大于当前元素运算符优先级
                                       //将栈顶运算符弹出加入到中转储蓄栈中
                                   transitStack.push(numStack.pop());
                                      //将当前元素保留进入下一轮对比
                               }else if (topElementPriority==1){
                                   //栈顶元素运算优先级小于或者等于当前运算符
                                       //需要将当前运算符入栈,然后继续遍历
                                   transitStack.push(numStack.pop());
                               }
                           }
                           break;
                       case 2://乘除
                              //对于乘除而言没有更高等级的运算符,无论是加减乘除还是左括号都直接将运算符压入到栈中
                              numStack.push(expression);
                              index++;
                           break;
                       case 3://右括号
                                   //遇到右括号,将栈中左括号之前元素全部弹出,加入到中转站中

                           while (util.styleOf(numStack.peek())!=4){
                                //将numstack中的左括号前的元素全部加到中转栈中
                                 transitStack.push(numStack.pop());
                           }
                           //将左括号弹出,消去一对括号
                           numStack.pop();
                           index++;
                           break;
                       case 4://左括号
                           numStack.push(expression);
                           index++;
                           break;
                   }
               }
               else{
                   //当前字符是数字,直接将数字压入中转栈
                   transitStack.push(expression);
                   index++;
               }


               System.out.println("--------开头----------");
            System.out.print("数字栈:");
               numStack.forEach(i-> System.out.print(i+" "));
            System.out.println();
            System.out.print("中转站:");
               transitStack.forEach(T-> System.out.print(T+" "));
            System.out.println("");
            System.out.println("-----------结尾------");
            System.out.println();
        }
            while(!numStack.empty())
                transitStack.push(numStack.pop());
        return transitStack;
    }
}
class ToSuffixUtil{
    public String[] expressionArray(String expression){
        String[] list = expression.split(" ");
        return list;
    }
    public int styleOf(String curr){
        if (curr.equals("("))
            return 4;
        else if (curr.equals(")"))
            return 3;
        else if (curr.equals("+")||curr.equals("-"))
            return 1;
        else if (curr.equals("*")||curr.equals("/"))
             return 2;
        else if (curr.matches("\\d+"))
            return 0;
        else
            throw new RuntimeException("运算符不正确,请检查输入的运算符");
    }
}